In recent years, communication networks have evolved to permit the commercially practical digital switching elements with combined time and space switching in the same chip or in the same printed circuit board. Communication networks that include such elements are called digital symmetrical matrix (DSM) networks. In a DSM network, information can be transferred from any channel of an incoming PCM link into any channel of an outgoing PCM link. P. Charransol, J. Haurl, C. Athensen, and D. Hardy, "Development of a Time Division Switching Network Usable in a Very Large Range of Capacities", IEEE Trans. Commun., vol. COM-27, No. 7, 1979, pp. 982-988, and A. Jajszczyk, "On Nonblocking Switching Networks Composed of Digital Symmetrical Matrices", IEEE Trans. Comm'n., Vol. COM-31, No. 1, 1983 describe blocking and non-blocking DSM networks of the type discussed herein.
One particularly interesting DSM network is the rearrangeably-blocked DSM network. A switching network is rearrangeable if its permitted states realize every assignment of inlets to outlets, or alternatively, if given any state x of the network, any inlet idle in x, and any outlet idle in x, there is a way of assigning new routes to the calls in progress in x so that the idle inlet can be connected to the idle outlet.
The DSM network may be described by the notation J(m, v, f.sub.o, u.sub.i, f.sub.i, r), where m is the number of middle switches, v is the number for group of PCM links between switches, f.sub.o and f.sub.i are numbers for the channels in a PCM link, u.sub.i is the number of PCM links, and r is the number of switches in the first and last stages. It has been shown that DSM network J(m, v, f.sub.o, u.sub.i, f.sub.i, r) is rearrangeable if and only if ##EQU1## The proof for the sufficiency of this condition is based on Hall's Theorem on distinct representatives of subsets and is, therefore, non-constructive. That is, this proof does not explain how to rearrange the rearrangeably-blocked DSM matrix in the event that this condition exists.
It is, therefore, an object of the present invention to provide an efficient rearrangement algorithm for rearrangeable DSM networks.
It is also an object of the present invention to provide a method and system that, for the DSM network J(m, v, f.sub.o, u.sub.i, f.sub.i, r), if ##EQU2## then given a non-realizable connection request, the present invention presents certain existing connections that can always be so rearranged that the connection request becomes realizable after the rearrangement.
To perform rearrangement of the DSM network, it is an object of the present invention to provide a method and system for constructing a connection tree, such as an O-tree, an I-tree, a modified O-tree, and a modified I-tree for a rearrangeably-blocked digital symmetrical matrix (DSM) network, where the DSM network has a plurality of input switch nodes, a plurality of middle switches, and a plurality of output switch nodes, and where the connection tree provides at least one feasible node for use in a rearrangement method for connecting the input switch nodes to the output switch nodes through said middle switches. The connection tree constructing method includes the steps of receiving a plurality of parameters including a tree forming instruction for forming the connection tree as an I-tree or an O-tree, an input switch parameter associated with an identified input switch node, an output switch parameter associated with an identified output switch node, a first middle switch parameter for associating a first middle switch with the identified input switch node, and a second middle switch parameter for associating a second middle switch with the identified output switch node.
The method has the further step of designating all input switch nodes as unvisited input switch nodes and all output switches nodes of the DSM as unvisited output switch nodes. Next, the method determines whether the tree forming instruction is for forming an I-tree or an O-tree and stores the input switch parameter in a queue in the event that the tree forming instruction is for forming an I-tree. Alternatively, the present invention stores the output switch parameter in the queue in the event that the tree forming instruction is for forming an O-tree. The embodiment further makes the input switch parameter an I-tree root in the event that the tree forming instruction is for forming an I-tree or, alternatively, makes the output switch parameter an O-tree root in the event that the tree forming instruction is for forming an O-tree.
The next step is to remove a current node parameter from the queue which may be either an input switch parameter or an output switch parameter, and identify a set of feasible input switch nodes in the event that the current node parameter is an input switch parameter. This feasible input node identifying step includes the steps of labeling the identified input switch node as a feasible input node in the event that there is an idle channel from the identified input switch to the second middle switch and identifying all output switch nodes that connect through the second middle switch to the identified input switch node, in the event that there is no idle channel from the identified input switch to the second middle switch.
Then the method makes all unvisited input switch nodes children of the identified input switch node and places input switch parameters associated with the unvisited input switch nodes in the queue and designates the identified input switch node as a visited input node, as well as marks the identified input switch node as a visited input node. The method performs similar steps to find feasible output switch nodes in the event that the current node parameter is an output switch parameter. These steps are repeated as long as the queue contains at least one input switch node parameter or at least one output switch parameter.
It is a further object of the present invention to provide not only an efficient rearrangement algorithm for the DSM networks, but also a simple control algorithm for the communication network using the rearrangeable DSM network.
A further object of the present invention is to provide parallelized version of the rearrangement algorithm that runs in 0(log r) steps on the CRCW (Concurrent-Read Concurrent-Write) PRAM model using only O(max(r.sup.3,m)) processors.
These and other objects will become apparent to the reader upon a reading and understanding of the following detailed description and claims.